#include <vector>
#include <string>
using namespace std;
    
// 汉罗塔问题
class Solution {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        dfs(A, B, C, A.size());
    }

    void dfs(vector<int>& a, vector<int> &b, vector<int>& c, int n)
    {
        if (n == 1)
        {
            c.push_back(a.back());
            a.pop_back();
            return;
        }
        dfs(a, c, b, n - 1);
        c.push_back(a.back());
        a.pop_back();
        dfs(b, a, c, n - 1);
        return;
    }
};
    
// 合并两个有序链表
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr) return list2;
        if (list2 == nullptr) return list1;
        if (list1->val <= list2->val)
        {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
        else
        {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;
        ListNode* newhead = swapPairs(head->next->next);
        ListNode* ret = head->next;
        head->next->next = head;
        head->next = newhead;
        return ret;
    }
};

// 快速幂
class Solution {
public:
    double myPow(double x, int n) {
        return n < 0 ? 1.0 / pow(x, -(long)n) : pow(x, n);
    }

    double pow(double x, long n)
    {
        if (n == 0) return 1;
        double num = pow(x, n / 2);
        return n % 2 == 0 ? num * num : num * num * x;
    }
};

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        return dfs(root, 0);
    }

    int dfs(TreeNode* root, int prevsum)
    {
        prevsum = prevsum * 10 + root->val;
        if (root->left == nullptr && root->right == nullptr) return prevsum;
        int ret = 0;
        if (root->left) ret += dfs(root->left, prevsum);
        if (root->right) ret += dfs(root->right, prevsum);
        return ret;
    }
};

// 二叉树剪枝
class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        if (root == nullptr) return nullptr;
        root->left = pruneTree(root->left);
        root->right = pruneTree(root->right);
        if (root->left == nullptr && root->right == nullptr && root->val == 0)
        {
            delete root;
            root = nullptr;
        }
        return root;
    }
};

// 二叉搜索树中第 K 小的元素
class Solution {
    int count = 0, ret = 0;
public:
    int kthSmallest(TreeNode* root, int k) {
        count = k;
        dfs(root);
        return ret;
    }
    void dfs(TreeNode* root)
    {
        if (root == nullptr || count == 0) return;
        dfs(root->left);
        if (--count == 0) ret = root->val;
        dfs(root->right);
    }
};

// 验证二叉搜索树
class Solution {
    long prev = LONG_MIN;
public:
    bool isValidBST(TreeNode* root) {
        if (root == nullptr) return true;
        bool left = isValidBST(root->left);
        if (left == false) return false;// 剪枝
        bool cur = false;
        if (root->val > prev) cur = true;
        if (cur == false) return false;// 剪枝
        prev = root->val;
        bool right = isValidBST(root->right);
        return left && right && cur;
    }
};


// 二叉树的所有路径
class Solution {
    vector<string> ret;
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        string path;
        dfs(root, path);// 利用传值传参回溯恢复现场
        return ret;
    }
    void dfs(TreeNode* root, string path)
    {
        path += to_string(root->val);
        if (root->left == nullptr && root->right == nullptr)// 叶子结点
        {
            ret.push_back(path);
            return;
        }
        path += "->";
        if (root->left) dfs(root->left, path);
        if (root->right) dfs(root->right, path);
    }
};

// 全排列 II
class Solution {
    vector<vector<int>> ret;
    vector<int> path;
    bool check[9];
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        dfs(nums, 0);
        return ret;
    }
    void dfs(vector<int>& nums, int pos)
    {
        if (pos == nums.size())
        {
            ret.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++)
        {
            if (check[i] == false && (i == 0 || nums[i] != nums[i - 1] 
                || check[i - 1] == true))
            {
                path.push_back(nums[i]);
                check[i] = true;
                dfs(nums, pos + 1);
                path.pop_back();
                check[i] = false;
            }
        }
    }
};

// 电话号码的字母组合
class Solution {
    string hash[10] = {"", "", "abc", "def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    vector<string> ret;
    string path;
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return ret;
        dfs(digits, 0);
        return ret;
    }
…            dfs(digits, pos + 1);
            path.pop_back();
        }
    }
};

// 括号生成
class Solution {
    int left = 0, right = 0;
    vector<string> ret;
    string path;
public:
    vector<string> generateParenthesis(int n) {
        dfs(n);
        return ret;
    }
    void dfs(int n)
…            path.pop_back(); left--;
        }
        if (right < left)
        {
            path.push_back(')'); right++;
            dfs(n);
            path.pop_back(); right--;
        }
    }
};

// 组合
class Solution {
    vector<vector<int>> ret;
    vector<int> path;
public:
    vector<vector<int>> combine(int n, int k) {
        dfs(n, k, 1);
        return ret;
    }
    void dfs(int& n, int& k, int pos)
    {
        if (path.size() == k)
        {
            ret.push_back(path);
            return;
        }
        for (int i = pos; i <= n; i++)
        {
            path.push_back(i);
            dfs(n, k, i + 1);
            path.pop_back();
        }
    }
};

// 目标和
class Solution {
    int path = 0, ret = 0;
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        dfs(nums, target, 0, 0);
        return ret;
    }
    void dfs(vector<int>& nums, int& target, int pos, int path)
    {
        if (pos == nums.size()) 
        {
            if (target == path) ret++;
            return;
        }
        // 加法
        dfs(nums, target, pos + 1, path + nums[pos]);
        // 减法
        dfs(nums, target, pos + 1, path - nums[pos]);
    }
};

// 组合总和
class Solution {
    vector<vector<int>> ret;
    vector<int> path;
    int aim;
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        aim = target;
        dfs(candidates, 0, 0);
        return ret;
    }
    void dfs(vector<int>& nums, int pos, int sum)
    {
        if (sum == aim)
        {
            ret.push_back(path);
            return;
        }
        if (sum > aim || pos == nums.size()) return;
        for (int i = pos; i < nums.size(); i++)
        {
            path.push_back(nums[i]);
            dfs(nums, i, sum + nums[i]);
            path.pop_back();
        }
    }
};

// 字母大小写全排列
class Solution {
    vector<string> ret;
    string path;
public:
    vector<string> letterCasePermutation(string s) {
        dfs(s, 0);
        return ret;
    }
    void dfs(const string& s, int pos)
    {
        if (pos == s.size())
        {
            ret.push_back(path);
            return;
        }
        char ch = s[pos];
        // 变
        if (ch > '9')
        {
            path.push_back(change(ch));
            dfs(s, pos + 1);
            path.pop_back();
        }
        // 不变
        path.push_back(ch);
        dfs(s, pos + 1);
        path.pop_back();
    }
    char change(char ch)
    {
        return ch >= 'a' ? ch - 32 : ch + 32;
    }
};

class Solution {
    int ret = 0, k = 0;
    bool check[16];
public:
    int countArrangement(int n) {
        k = n;
        dfs(1);
        return ret;
    }
    void dfs(int pos)
    {
        if (pos == k + 1)
        {
            ret++;
            return;
        }
        for (int i = 1; i <= k; i++)
        {
            if (check[i] == false && (i % pos == 0 || pos % i == 0))
            {
                check[i] = true;
                dfs(pos + 1);
                check[i] = false;
            }
        }
    }
};

// N皇后
class Solution {
    vector<vector<string>> ret;
    vector<string> path;
    bool checkCol[10] = {}, checkDig1[20] = {}, checkDig2[20] = {};
public:
    vector<vector<string>> solveNQueens(int n) {
        path.resize(n);
        for (int i = 0; i < n; i++) path[i].append(n, '.');
        dfs(0, n);
        return ret;
    }
    void dfs(int row, int n)
    {
        if (row == n)
        {
            ret.push_back(path);
            return;
        }
        // 尝试在这一行放皇后
        for (int col = 0; col < n; col++)
        {
            // 剪枝
            if (!checkCol[col] && !checkDig1[col - row + n] && !checkDig2[col + row])
            {
                path[row][col] = 'Q';
                checkCol[col] = checkDig1[col - row + n] = checkDig2[col + row] = true;
                dfs(row + 1, n);
                path[row][col] = '.';
                checkCol[col] = checkDig1[col - row + n] = checkDig2[col + row] = false;
            }
        }
    }
};

// 有效的数独
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        bool row[9][10] = {};
        bool col[9][10] = {};
        bool grid[3][3][10] = {};
        for (int i = 0; i < board.size(); i++)
            for (int j = 0; j < board[0].size(); j++)
                if (board[i][j] != '.')
                {
                    int num = board[i][j] - '0';
                    if (row[i][num] || col[j][num] || grid[i / 3][j / 3][num])
                        return false;
                    row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
                }
        return true;
    }
};

// 解数独
class Solution {
    bool row[9][10] = {};
    bool col[9][10] = {};
    bool grid[3][3][10] = {};
public:
    void solveSudoku(vector<vector<char>>& board) {
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++)
                if (board[i][j] != '.') 
                {
                    int num = board[i][j] - '0';
                    row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
                }
        dfs(board);
    }
    bool dfs(vector<vector<char>>& board)
    {
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++)
                if (board[i][j] == '.')
                {
                    for (int k = 1; k < 10; k++)
                    {
                        if (!row[i][k] && !col[j][k] && !grid[i / 3][j / 3][k]) 
                        {
                            board[i][j] = k + '0';
                            row[i][k] = col[j][k] = grid[i / 3][j / 3][k] = true;
                            if (dfs(board)) return true;
                            board[i][j] = '.';
                            row[i][k] = col[j][k] = grid[i / 3][j / 3][k] = false;
                        }
                    }
                    return false;
                }
        return true;;
    }
};

// 单词搜索
class Solution {
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    int m, n;
    bool check[7][7] = {};
public:
    bool exist(vector<vector<char>>& board, string word) {
        m = board.size();
        n = board[0].size();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (board[i][j] == word[0])
                {
                    check[i][j] = true;
                    if (dfs(board, i, j, 1, word)) return true;
                    check[i][j] = false;
                }
        return false;
    }
    bool dfs(vector<vector<char>>& b, int i, int j, int pos, string& word)
    {
        if (pos == word.size()) return true;
        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n 
                && check[x][y] == false && b[x][y] == word[pos])
            {
                check[x][y] = true;
                if (dfs(b, x, y, pos + 1, word)) return true;
                check[x][y] = false;
            }
        }
        return false;
    }
};

// 黄金矿工
class Solution {
    int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
    int m, n, ret = 0;
    bool check[16][16] = {};
public:
    int getMaximumGold(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j])
                {
                    check[i][j] = true;
                    dfs(grid, i, j, grid[i][j]);
                    check[i][j] = false;
                }
        return ret;
    }
    void dfs(vector<vector<int>>& grid, int i, int j, int path)
    {
        ret = max(ret, path);
        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] && !check[x][y])
            {
                check[x][y] = true;
                dfs(grid, x, y, path + grid[x][y]);
                check[x][y] = false;
            }
        }
    }
};

// 不同路径 III
class Solution {
    int m, n, ret, count;
    bool check[21][21] = {};
    int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
public:
    int uniquePathsIII(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        int x, y;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 0) count++;
                if (grid[i][j] == 1) x = i, y = j;
            }
        dfs(grid, x, y, 0);
        return ret;
    }
    void dfs(vector<vector<int>>& grid, int x, int y, int path)
    {
        for (int k = 0; k < 4; k++)
        {
            int a = x + dx[k], b = y + dy[k];
            if (a >= 0 && a < m && b >= 0 && b < n && !check[a][b])
            {
                if (!grid[a][b])
                {
                    check[a][b] = true;
                    dfs(grid, a, b, path + 1);
                    check[a][b] = false;
                }
                if (grid[a][b] == 2 && count == path) ret++;
            }
        }
    }
};

// 图像渲染（dfs)
class Solution {
    int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
    int _color, m, n, target;
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        if (image[sr][sc] == color) return image;
        _color = color;
        m = image.size(), n = image[0].size();
        target = image[sr][sc];
        dfs(image, sr, sc);
        return image;
    }
    void dfs(vector<vector<int>>& image, int x, int y)
    {
        image[x][y] = _color;
        for (int i = 0; i < 4; i++)
        {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < m && b >= 0 && b < n && image[a][b] == target)
            {
                dfs(image, a, b);
            }
        }
    }
};

// 岛屿数量
class Solution {
    int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
    bool check[301][301] = {};
    int ret, m, n;
public:
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == '1' && !check[i][j])
                {
                    ret++;
                    check[i][j] = true;
                    dfs(grid, i, j);
                }
        return ret;
    }
    void dfs(vector<vector<char>>& grid, int i, int j)
    {
        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' && !check[x][y])
            {
                check[x][y] = true;
                dfs(grid, x, y);
            }
        }
    }
};

// 岛屿的最大面积
class Solution {
    int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
    bool check[51][51] = {};
    int ret = 0, area, m, n;
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == 1 && !check[i][j])
                {
                    area = 0;
                    check[i][j] = true;
                    dfs(grid, i, j);
                    ret = max(ret, area);
                }
        return ret;
    }
    void dfs(vector<vector<int>>& grid, int i, int j)
    {
        area++;
        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && !check[x][y] && grid[x][y] == 1)
            {
                check[x][y] = true;
                dfs(grid, x, y);
            }
        }
    }
};

// 被围绕的区域
class Solution {
    int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
    bool check[201][201] = {};
    int m, n;
public:
    void solve(vector<vector<char>>& board) {
        m = board.size(), n = board[0].size();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) 
                    && board[i][j] == 'O' && !check[i][j])
                {
                    check[i][j] = true;
                    dfs(board, i, j);
                }
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (board[i][j] == 'O' && !check[i][j])
                    board[i][j] = 'X';
    }
    void dfs(vector<vector<char>>& board, int i, int j)
    {
        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O' && !check[x][y])
            {
                check[x][y] = true;
                dfs(board, x, y);
            }
        }
    }
};

// 太平洋大西洋水流问题
class Solution {
    int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
    vector<vector<int>> ret;
    int m, n;
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        m = heights.size(), n = heights[0].size();
        bool pac[201][201] = {};
        bool atl[201][201] = {};
        for (int i = 0; i < m; i++) 
        {
            if (!pac[i][0]) dfs(heights, i, 0, pac);
            if (!atl[i][n - 1]) dfs(heights, i, n - 1, atl);
        }
        for (int j = 0; j < n; j++) 
        {
            if (!pac[0][j]) dfs(heights, 0, j, pac);
            if (!atl[m - 1][j]) dfs(heights, m - 1, j, atl);
        }
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (pac[i][j] && atl[i][j]) ret.push_back({i, j});
        return ret;
    }
    void dfs(vector<vector<int>>& h, int i, int j, bool check[][201])
    {
        check[i][j] = true;
        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && !check[x][y] && h[x][y] >= h[i][j])
            {
                check[x][y] = true;
                dfs(h, x, y, check);
            }
        }
    }
};

// 扫雷游戏
class Solution {
    int dx[8] = {1, -1, 0, 0, 1, 1, -1, -1};
    int dy[8] = {0, 0, 1, -1, 1, -1, 1, -1};
    int m, n;
public:
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        m = board.size(), n = board[0].size();
        int x = click[0], y = click[1];
        if (board[x][y] == 'M') // 第一步就点到地雷
        {
            board[x][y] = 'X';
            return board;
        }
        dfs(board, x, y);
        return board;
    }
    void dfs(vector<vector<char>>& board, int i, int j)
    {
        int count = 0;
        for (int k = 0; k < 8; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M')
                count++;
        }
        if (count) board[i][j] = count + '0';
        else // 展开所有空方块
        {
            board[i][j] = 'B';
            for (int k = 0; k < 8; k++)
            {
                int x = i + dx[k], y = j + dy[k];
                if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E')
                {
                    dfs(board, x, y);
                }
            }
        }
    }
};

// 机器人的运动范围
class Solution {
    int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
    bool check[101][101] = {};
    int ret, m, n, cnt;
public:
    int wardrobeFinishing(int _m, int _n, int _cnt) {
        m = _m, n = _n, cnt = _cnt;
        dfs(0, 0);
        return ret;
    }
    void dfs(int i, int j)
    {
        ++ret;
        check[i][j] = true;
        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && sum(x, y) && !check[x][y])
            {
                dfs(x, y);
            }
        }
    }
    bool sum(int x, int y)
    {
        int tmp = 0;
        while (x)
        {
            tmp += x % 10;
            x /= 10;
        }
        while (y)
        {
            tmp += y % 10;
            y /= 10;
        }
        return tmp <= cnt;
    }
};

// 斐波那契数
// 记忆化搜索
class Solution {
    int memory[31];
public:
    int fib(int n) {
        memset(memory, -1, sizeof(memory));
        return dfs(n);
    }
    int dfs(int n)
    {
        if (memory[n] != -1) return memory[n]; // 剪枝
        if (n == 0 || n == 1) 
        {
            memory[n] = n; // 返回之前存进备忘录
            return n;
        }
        memory[n] = dfs(n - 1) + dfs(n - 2); // 存进备忘录
        return memory[n];
    }
};
// 动态规划
class Solution {
    int dp[31];
public:
    int fib(int n) {
        dp[0] = 0, dp[1] = 1;
        for (int i = 2; i <= n; i++)
            dp[i] = dp[i - 1] + dp[i - 2];
        return dp[n];
    }
};

// 最长递增子序列
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        // 动态规划
        int n = nums.size();
        vector<int> dp(n, 1); // 子序列的长度最小是自己
        int ret = 0;
        for (int i = n - 1; i >= 0; i--) // 从后往前填表
        {
            for (int j = i + 1; j < n; j++) // 这个位置后面的最长子序列
            {
                if (nums[j] > nums[i])
                {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            // 上面这个循环统计的是dp[i]这个位置后面的最长子序列
            ret = max(ret, dp[i]); // 以每一个为起点的最长递增子序列
        }
        return ret;

        // 记忆化搜索
        // vector<int> memo(nums.size());
        // int ret = 0;
        // for (int i = 0; i < nums.size(); i++)
        // {
        //     // 以任意为起点的最长子序列中的最大值
        //     ret = max(ret, dfs(nums, i, memo));
        // }
        // return ret;
    }
    int dfs(vector<int>& nums, int pos, vector<int>& memo)
    {
        if (memo[pos] != 0) return memo[pos];
        int ret = 1;
        for (int i = pos + 1; i < nums.size(); i++)
        {
            if (nums[i] > nums[pos])
            {
                // 以这个位置为起点的最长子序列的最大值
                ret = max(ret, dfs(nums, i, memo) + 1);
            }
        }
        memo[pos] = ret;
        return ret;
    }
};

// 猜数字大小
class Solution {
    int memo[201][201];
public:
    int getMoneyAmount(int n) {
        return dfs(1, n); // dfs帮我们返回这个区间中能让我们胜利的最小值
    }
    int dfs(int left, int right)
    {
        if (left >= right) return 0;
        if (memo[left][right] != 0) return memo[left][right];
        int ret = INT_MAX;
        for (int head = left; head <= right; head++) // 每个数都作为头节点尝试一遍
        {
            int x = dfs(left, head - 1);
            int y = dfs(head + 1, right);
            ret = min(ret, head + max(x, y));
        }
        memo[left][right] = ret;
        return ret;
    }
};

// 矩阵中的最长递增路径
class Solution {
    int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
    int memory[201][201];
    int m, n;
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        m = matrix.size(), n = matrix[0].size();
        int ret = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                ret = max(ret, dfs(matrix, i, j));
            }
        }
        return ret;
    }
    int dfs(vector<vector<int>>& matrix, int i, int j)
    {
        if (memory[i][j] != 0) return memory[i][j];
        int ret = 1;
        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j])
            {
                ret = max(ret, dfs(matrix, x, y) + 1);
            }
        }
        memory[i][j] = ret;
        return ret;
    }
};